//你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row,
// col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你
//每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。 
//
// 一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。 
//
// 请你返回从左上角走到右下角的最小 体力消耗值 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
//输出：2
//解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
//这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
//输出：1
//解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。
// 
//
// 示例 3： 
//
// 
//输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
//输出：0
//解释：上图所示路径不需要消耗任何体力。
// 
//
// 
//
// 提示： 
//
// 
// rows == heights.length 
// columns == heights[i].length 
// 1 <= rows, columns <= 100 
// 1 <= heights[i][j] <= 10⁶ 
// 
// Related Topics深度优先搜索 | 广度优先搜索 | 并查集 | 数组 | 二分查找 | 矩阵 | 堆（优先队列） 
//
// 👍 298, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import sun.security.util.math.IntegerModuloP;

import java.util.*;

class PathWithMinimumEffort {
    public static void main(String[] args) {
        Solution solution = new PathWithMinimumEffort().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 参照labuladong:https://labuladong.github.io/algo/2/21/56/
    class Solution {
        // Dijkstra 算法，计算 (0, 0) 到 (m - 1, n - 1) 的最小体力消耗
        public int minimumEffortPath(int[][] heights) {
            int m = heights.length, n = heights[0].length;
            int[][] disTo = new int[m][n];
            for (int i = 0; i < m; i++) {
                Arrays.fill(disTo[i], Integer.MAX_VALUE);
            }
            PriorityQueue<Status> queue = new PriorityQueue<>((a, b) -> a.effortFromStart - b.effortFromStart);
            disTo[0][0] = 0;
            queue.offer(new Status(0, 0, 0));

            while (!queue.isEmpty()) {
                Status status = queue.poll();
                int curX = status.x;
                int curY = status.y;
                int curEffortFromStart = status.effortFromStart;

                // 找到终点直接推出
                if (curX == m - 1 && curY == n - 1) return curEffortFromStart;

                // 如果有更小的路径，直接跳过
                if (curEffortFromStart > disTo[curX][curY]) continue;

                for (int[] height : adj(heights, curX, curY)) {
                    int nextX = height[0];
                    int nextY = height[1];
                    int nextEffortFromStart = Math.max(disTo[curX][curY], Math.abs(heights[nextX][nextY] - heights[curX][curY]));
                    if (disTo[nextX][nextY] > nextEffortFromStart) {
                        disTo[nextX][nextY] = nextEffortFromStart;
                        queue.offer(new Status(nextX, nextY, nextEffortFromStart));
                    }
                }
            }

            return -1;
        }

        class Status {
            int x;
            int y;
            int effortFromStart;

            public Status(int x, int y, int effortFromStart) {
                this.x = x;
                this.y = y;
                this.effortFromStart = effortFromStart;
            }

            public Status() {
            }
        }

        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        // 返回坐标 (x, y) 的上下左右相邻坐标
        List<int[]> adj(int[][] matrix, int x, int y) {
            int m = matrix.length, n = matrix[0].length;
            List<int[]> graph = new ArrayList<>();
            for (int[] dir : dirs) {
                int x1 = x + dir[0];
                int y1 = y + dir[1];

                if (x1 < 0 || y1 < 0 || x1 >= m || y1 >= n) continue;
                graph.add(new int[]{x1, y1});
            }

            return graph;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
